2631. Максимальный НОД

Дано n целых чисел. Найдите максимальное значение НОД (наибольшего общего делителя) среди всех пар этих чисел.

Вход. Первая строка содержит количество тестов t (1 ≤ t ≤ 100).

Следующие t строк представляют собой t тестов. Каждый тест содержит n (1 ≤ n ≤ 100) натуральных чисел.

Выход. Для каждого теста в отдельной строке выведите максимальное значение НОД среди всех возможных пар чисел.

Пример входа	Пример выхода
3 10 20 30 40 7 5 12 125 15 25	20 1 25

РЕШЕНИЕ

НОД

Анализ алгоритма

Прочитаем все числа для каждого теста в массив m. Далее переберем все пары чисел m_i и m_j (i < j) и найдем наибольшее значение среди НОД(m_i, m_j).

Пример

Для первого теста максимум достигается на паре НОД(20, 40) = 20.

Во втором тесте все числа являются взаимно простыми.

Для третьего теста максимум достигается на паре НОД(125, 25) = 25.

Реализация алгоритма

Читаем количество тестов tests.

scanf("%d", &tests);

while (tests--)

{

Обрабатываем очередной тест. Все числа теста читаем в массив m.

m.clear();

После каждого числа x читаем следующий символ ch. Как только ch станет равным ‘\n’, завершаем цикл.

while (scanf("%d%c", &x, &ch), ch != '\n')

m.push_back(x);

При этом не забываем занести последнее прочитанное значение x в массив m.

m.push_back(x);

Перебираем пары чисел m_i и m_j (i < j). Находим максимум среди НОД(m_i, m_j).

res = 1;

for (i = 0; i < m.size(); i++)

for (j = i + 1; j < m.size(); j++)

res = max(res, gcd(m[i], m[j]));

Выводим ответ.

printf("%d\n", res);

}